package main

import "fmt"

//循环版本
func fib1(n int) int {
	switch {
	case n < 0:
		panic("n is not negative")
	case n == 0:
		return 0
	case n == 1 || n == 2:
		return 1
	}
	a, b := 1, 1
	for i := 0; i < n-2; i++ {
		a, b = b, a+b
	}
	return b
}

// 公式化递归
func fib2(n int) int {
	if n < 3 {
		return 1
	}
	return fib2(n-1) + fib2(n-2)
}

// 循环改递归
func fib3(n, a, b int) int {
	if n < 3 {
		return b
	}
	return fib3(n-1, b, a+b)
}

func main() {
	// //循环版本
	// for i := 1; i < 20; i++ {
	// 	fmt.Println(fib1(i))
	// }

	// // 公式化递归
	// fmt.Println(fib2(11))

	fmt.Println(fib3(45, 1, 1))
}
